// 处理散列表冲突的几种方法：
// 1、分离链接
// 分离链接法包括
// 为散列表的每一个位置创建一个链表并将元素存储在里面。
// 它是解决冲突的最简单的方法，
// 但是它在HashTable实例之外还需要额外的存储空间

function HashTable(){
  var table = [];

  var loseloseHashCode = function(key){
    var hash = 0;
    for(var i = 0; i < key.length; i++){
      hash += key.charCodeAt(i);
    }
    return hash % 37;
  }

  var ValuePair = function(key, value){
    this.key = key;
    this.value = value;

    this.toString = function(){
      return '[' + this.key + ' - ' + this.value + ']';
    }
  }

  this.put = function(key, value){
    var position = loseloseHashCode(key);

    if(table[position] == undefined){
      table[position] = new LinkedList();
    }
    table[position].append(new ValuePair(key, value));
  }

  this.remove = function(key){
    var position = loseloseHashCode(key);

    if(table[position] !== undefined){
      var current = table[position].getHead();
      while(current.next){
        if(current.element.key === key){
          table[position].remove(current.element);
          if(table[position].isEmpty()){ // 如果移除后没有元素了
            table[position] = undefined;
          }
          return true;
        }
        current = current.next;
      }
      
      if(current.element.key === key){
        table[position].remove(current.element);
        if(table[position].isEmpty()){
          table[position] = undefined;
        }
        return true;
      }
    }
    return false;
  }

  this.get = function(key){
    var position = loseloseHashCode(key);

    if(table[position] !== undefined){
      // 遍历链表来寻找键/值
      var current = table[position].getHead();

      while(current.next){
        if(current.element.key === key){
          return current.element.value;
        }
        current = current.next;
      }

      // 检查元素在链表第一个或最后一个节点的情况
      if(current.element.key === key){
        return current.element.value;
      }
    }
    return undefined;
  }
}

function LinkedList(){

  /**
   * 链表元素的构造函数
   * @param {Any} element 元素本身
   */
  var Node = function(element){
    this.element = element;
    this.next = null;
  }

  var head = null; // 链表头
  var length = 0;  // 链表的长度

  this.append = function(element) {
    var node = new Node(element);
    if(head === null){
      head = node;
    } else {
      var current = head;
      while(current.next){
        current = current.next;
      }
      current.next = node;
    }
    return ++length;
  }

  this.insert = function(element, position = 0) {
    if(position >= length) {
      return this.append(element);
    } else if (position < 0) {
      console.error(`position can't be negative`);
      return false;
      
      // 或者可以处理成下面的样子
      
      if(length === 0){ // 防止进入下面的循环后出不来
        return this.append(element);
      }

      while(position < 0) {
        position += length;
      }
    }

    var node = new Node(element);
    var current = head;
    var previous = null;

    for(var i = 0; i < position; i++){
      previous = current;
      current = current.next;
    }
    
    node.next = current;
    if (!previous){
      head = node;
    } else {
      previous.next = node;
    }
    
    return ++length;
  }

  this.removeAt = function(position){
    if(position >= length || position < 0){
      console.warn('超出范围');
      return null;
    } else {
      var current = head;
      var previous = null;
      if(position === 0){
        head = current.next;
      } else {
        for(var i = 0; i < position; i++){
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      length--;
      return current.element;
    }
  }

  this.remove = function(element){
    this.removeAt(this.indexOf(element));
  }

  this.indexOf = function(element){
    var current = head;
    var i = 0;
    while(current){
      if(current.element === element){
        return i;
      }
      current = current.next;
      i++;
    }
    return -1;
  }

  this.isEmpty = function(){
    return length === 0;
  }

  this.size = function(){
    return length;
  }

  this.clear = function(){
    head = null;
    length = 0;
  }

  this.toString = function(){
    var str = '';
    var current = head;
    while(current){
      str += current.element;
      current = current.next;
    }
    return str;
  }

  this.getHead = function(){
    return head;
  }

}